package DP;

import java.util.*;

/**
 * 139.单词拆分
 * 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
 * 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
 * dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。
 * if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true
 */
public class wordBreak {
    /**
     * 一刷二刷思路一致，不做记录
     */
    //版本一
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>(wordDict);
        boolean[] valid = new boolean[s.length() + 1];
        valid[0] = true;

        for (int i = 1; i <= s.length(); i++) {//先遍历背包
            for (int j = 0; j < i && !valid[i]; j++) {  //遍历物品
                if (set.contains(s.substring(j, i)) && valid[j]) {
                    valid[i] = true;
                }
            }
        }

        return valid[s.length()];
    }

    //版本二，更容易理解
    public boolean wordBreak1(String s, List<String> wordDict) {
        Boolean dp[] = new Boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (String word : wordDict) {
                int len = word.length();
                if (i >= len && dp[i - len] && word.equals(s.substring(i - len, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

    /**
     * hot100一刷
     */
    public boolean wordBreak2(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        Arrays.fill(dp, false);
        dp[0] = true;
        for (int i = 1; i < dp.length; i++) {
            for (String str : wordDict) {
                int len = str.length();
                if (i >= len && str.equals(s.substring(i - len, i)) && dp[i - str.length()]) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }
}
